
\begin{algorithm}
   \caption{The CKY Algorithm for Chart Parsing (with Back-Pointers)}
   \label{alg:cky}
\begin{algorithmic}[1]
   \For{$i = 1 \to n$}  
      \For{$L= 1 \to |\mathcal{N}|$}
         \State $\delta_L [i-1,i] \gets p(A_L\rightarrow w_{i}|A_L)$    \Comment{Initiate pre-terminal probs}
         \State $\beta_L [i] \gets   \langle w_i \rangle $    \Comment{Store words}
      \EndFor
   \EndFor
   \For{$span= 2 \to n$}  \Comment{Fill in  the chart}
      \For{$end= span \to n$}
        \State{$begin \gets end - span$}
           \For{$L= 1 \to |\mathcal{N}|$} 
           \State $\delta_L (begin,end) \gets \text{max}_{\langle m,J,K\rangle } p(A_L\rightarrow A_J A_K|A_L) \times \delta_J(begin,m) \times \delta_K(m,end)$
           \State $\beta_L (begin,end) \gets   \text{argmax}_{\langle m,J,K\rangle } p(A_L\rightarrow A_J A_K|A_L) \times \delta_J(begin,m) \times \delta_K(m,end)$
         \EndFor   
      \EndFor
   \EndFor
   \State  
   {\bf return} {\sc Reconstruct-Tree} 
   %{\sc Build-Tree}
   ($\delta_S[0,n], \beta_S[0,n]$) 
    \Comment{Follow back-pointers}
    \end{algorithmic}
\end{algorithm}


\begin{algorithm}
   \caption{The CKY Algorithm for Lattice Parsing (with Back-Pointers)}
   \label{alg:cky}
\begin{algorithmic}[1]
   \For{$\langle i,A_L,j \rangle \in \Call{Edges}{MA(x)}$}   \Comment{traverse the morphological analysis lattice}
      %\For{$L= 1 \to |\mathcal{N}|$}
         \State $\delta_{A_L} [i,j] \gets p(A_L\rightarrow s_{i,j})$    \Comment{Initiate segments probs}
         \State $\beta lattice_{A_L} [i,j] \gets   \langle s_{i,j} \rangle $    \Comment{Store segments}
      %\EndFor
   \EndFor
   \For{$span= 2 \to n$}  \Comment{Fill in  the chart}
      \For{$end= span \to n$}
        \State{$begin \gets end - span$}
           \For{$L= 1 \to |\mathcal{N}|$} 
           \State $\delta_L (begin,end) \gets \text{max}_{\langle m,J,K\rangle } p(A_L\rightarrow A_J A_K) \times \delta_J(begin,m) \times \delta_K(m,end)$
           \State $\beta_L (begin,end) \gets   \text{argmax}_{\langle m,J,K\rangle } p(A_L\rightarrow A_J A_K) \times \delta_J(begin,m) \times \delta_K(m,end)$
         \EndFor   
      \EndFor
   \EndFor
   \State {\bf return} {\sc Build-Tree} {$\delta_S[0,n]), \beta_S[0,n]$}  \Comment{Follow back-pointers}
    \end{algorithmic}
\end{algorithm}



\begin{algorithm}
   \caption{The Transform-Detransform method for history-based PCFG parsing  }
   \label{alg:cky}
\begin{algorithmic}[1]
%\Input  Input: original-treebank, divided into train-set and test-set
       \State trans-trainset $\gets$ {\sc Transform}(original-trainset) \Comment enrich treebank trees
       \State grammar $\gets$ {\sc Train}(trans-trainset) \Comment obtain a probabilistic grammar
          \For{$i= 1 \to n$} \Comment traverse the  test-set
          \State  $tree_i \gets$ {\sc Decode}$ (grammar,x_i)$ \Comment parse the input sentence
          \State $ y_i \gets$ {\sc De-transform}$(tree_i)$ \Comment discard enrichment
          \EndFor
          \State {\bf return} $\{y_i\}_{1}^n$ \Comment return prediction
    \end{algorithmic}
\end{algorithm}

